package util;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Tree.java
 * @Author : WangRuoyu
 * @Date 2023/10/22 16:31
 */

public class Tree {

    public static String[] tree;

    public static int cnt;

    private static TreeNode preorderCreateTree(TreeNode father, int tag) {
        TreeNode node = null;
        if (tree[cnt] != null) {
            node = new TreeNode(Integer.parseInt(tree[cnt]));
            cnt++;
            if (father != null) {
                if (tag == 0) {
                    father.left = node;
                } else {
                    father.right = node;
                }
            }
            preorderCreateTree(node, 0);
            preorderCreateTree(node, 1);
        } else {
            cnt++;
        }
        return node;
    }

    /***
     * 先序创建二叉树（字符串数组）
     * ***/
    public static TreeNode createTreeByPreorder(String[] tree) {
        Tree.tree = tree;
        cnt = 0;
        return preorderCreateTree(null, 0);
    }


    /***
     * 先序中序创建二叉树（整数数组）
     * ***/
    public static TreeNode createTreeByPreorderAndInorder(int[] preorder, int[] inorder) {
        return preorderAndInorderCreateTree(preorder, inorder, 0, preorder.length - 1, 0, preorder.length - 1);
    }

    private static TreeNode preorderAndInorderCreateTree(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2) {
        if (l1 > r1) return null;
        TreeNode node = new TreeNode(preorder[l1]);
        int k = l2;
        for (; k <= r2; k++) {
            if (inorder[k] == node.val) break;
        }
        node.left = preorderAndInorderCreateTree(preorder, inorder, l1 + 1, l1 + k - l2, l2, k - 1);
        node.right = preorderAndInorderCreateTree(preorder, inorder, l1 + k - l2 + 1, r1, k + 1, r2);
        return node;
    }

    /***
     * 中序后序创建二叉树（整数数组）
     * ***/
    public static TreeNode createTreeByPostorderAndInorder(int[] postorder, int[] inorder) {
        return postorderAndInorderCreateTree(postorder, inorder, 0, inorder.length - 1, 0, inorder.length - 1);
    }

    private static TreeNode postorderAndInorderCreateTree(int[] postorder, int[] inorder, int l1, int r1, int l2, int r2) {
        if (l1 > r1) return null;
        TreeNode node = new TreeNode(postorder[r1]);
        int k = l2;
        for (; k <= r2; k++) {
            if (inorder[k] == node.val) break;
        }
        node.left = postorderAndInorderCreateTree(postorder, inorder, l1, l1 + k - l2 - 1, l2, k - 1);
        node.right = postorderAndInorderCreateTree(postorder, inorder, l1 + k - l2, r1 - 1, k + 1, r2);
        return node;
    }

    /***
     * 先序遍历二叉树
     * ***/
    public static void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    /***
     * 中序遍历二叉树
     * ***/
    public static void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

    /***
     * 后序遍历二叉树
     * ***/
    public static void postorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}

